package demo1;

public class HashBuck {
    static class node{
        int key;
        int val;
        node next;
        public node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    public int useSized;
    public static final double factor=7.5;
    public node[] arr=new node[10];
    public void push(int key,int val){
        int index=key% arr.length;
        node cur=arr[index];
        while(cur!=null){
            if(cur.key==key){//查看原数组中有没有对应的节点的key与要插入key相同的，若有更新其存储值
                cur.val=val;
                return;//更新后返回
            }
            cur=cur.next;
        }
        node n=new node(key,val);//作为新节点放入
        n.next=arr[index];//头插
        arr[index]=n;
        useSized++;
        if(dofactor()>=factor){//负载因子大于7.5时要扩容
            resize();
        }
    }
    private  double dofactor(){
        return useSized/ arr.length;
    }
    private void resize(){
        node[] arr2=new node[2* arr.length];//扩容
        for(int i=0;i<arr.length;i++) {//把每一个节点放在它们该去的位置，在扩容后
            node cur=arr[i];//不改变原节点
            while(cur!=null){//把每个数组元素中链表节点走完
                int newindex=cur.key% arr.length;//重算cur应在的新数组的下标
                node curn=cur.next;//防止下面修改节点位置时找不到原节点的下一个节点位置，故先存起来
                cur.next=arr2[newindex];//头插
                arr2[newindex]=cur;
                cur=curn;//移动到下一个节点计算
            }
        }
        arr=arr2;
    }
    //根据key值获取val值
    public void  getval(int key){
        int index=key% arr.length;
        node cur=arr[index];
        while(cur!=null){
            if(cur.key==key){
                System.out.println(key+"对应val值为："+ cur.val);
                return;
            }
            cur=cur.next;
        }
        System.out.println("没找到key对应的val值");
    }
//打印
    public void display(){
        for(int i=0;i< arr.length;i++){
            node cur=arr[i];
            while(cur!=null){
                System.out.println("key值："+cur.key+"    val值："+cur.val);
                cur=cur.next;
            }
        }
    }
}
